package net.tp.algo.graph.shortestpath;

import net.tp.algo.graph.Graph;
import net.tp.algo.graph.TopologicalSort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 *
 * @author Trung Phan
 */
public class WeightedDAG {

    private double[] distanceTo;

    private int[] edgeTo;

    private boolean hasCycle;

    private final int source;

    public WeightedDAG(Graph graph, int source) {

        int N = graph.order();

        this.source =source;

        List<Integer> vertices = TopologicalSort.sort(graph);

        if (vertices.isEmpty()) {
            this.hasCycle = true;
        }
        else {
            this.distanceTo = new double[N];
            Arrays.fill(distanceTo, Double.MAX_VALUE);

            this.edgeTo = new int[N];
            Arrays.fill(edgeTo, -1);

            this.distanceTo[source] = 0;

            for (int u : vertices) {

                if (distanceTo[u] == Double.MAX_VALUE) continue;

                for (Graph.Edge edge : graph.edges(u)) {
                    int w = edge.other(u);
                    if (distanceTo[w] > distanceTo[u] + edge.weight()) {
                        distanceTo[w] = distanceTo[u] + edge.weight();
                        edgeTo[w] = u;
                    }
                }
            }
        }
    }

    public double distanceTo(int w) {
        if (hasCycle) {
            throw new IllegalStateException("The graph is not a DAG.");
        }
        return distanceTo[w];
    }

    public List<Integer> pathTo(int w) {
        if (hasCycle) {
            throw new IllegalStateException("The graph is not a DAG.");
        }

        if (distanceTo[w] == Double.MAX_VALUE) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();
        for (; w != source; w = edgeTo[w]) {
            result.add(0, w);
        }
        result.add(0, source);

        return result;
    }


}
